package leetcode81_90;

import outoforder.leetcode.ListNode;

/**
 * @author shhjiang_001
 * @create 2020-06-26 20:32
 */
        /*
        给定一个链表和一个特定值 x，对链表进行分隔，
        使得所有小于 x 的节点都在大于或等于 x 的节点之前。
        你应当保留两个分区中每个节点的初始相对位置。

        示例:

        输入: head = 1->4->3->2->5->2, x = 3
        输出: 1->2->2->4->3->5
        */

public class Solution86 {
    public ListNode partition(ListNode head, int x) {
        ListNode resLeNode = new ListNode();
        ListNode leTemp = resLeNode;
        ListNode resRiNode = new ListNode();
        ListNode riTemp = resRiNode;
        while(head != null){
            if(head.val < x){
                leTemp.next = new ListNode();
                leTemp = leTemp.next;
                leTemp.val = head.val;
            }else{
                riTemp.next = new ListNode();
                riTemp = riTemp.next;
                riTemp.val = head.val;
            }
            head = head.next;
        }
        if(resRiNode.next != null){
            leTemp.next = resRiNode.next;
        }
        return resLeNode.next;
    }

}
